3.13.5. Реализация помехоустойчивого кодирования.

         Предположим, что информация представлена в виде двоичной (закодированной двоично) информации, т. е. в виде последовательности нулей и единиц, и подлежит передаче по каналу, подверженному случайным ошибкам. Задача кодирования состоит в таком добавлении к информационным символам дополнительных символов, чтобы на приемнике эти искажения могли быть найдены и исправлены. Иначе говоря, последовательность символов данных представляется в виде некоторой более длинной последовательности символов, избыточность которой достаточна для защиты данных.
         Двоичный код мощности М и длины n представляет собой множество из М двоичных слов длины n, называемых кодовыми словами. Обычно М = 2^к, где к - некоторое целое число. Такой код называется двоичным n,к-кодом. Например, можно построить следующий код: 10101 10010 01110 11111. Это очень "бедный" (и очень маленький) код с М = 4 и n = 5, но он удовлетворяет приведенному выше определению. Данный код можно использовать для представления 2-битовых двоичных чисел, используя следующее (произвольное) соответствие: 00 - 10101, 01 - 10010, 10 - 01110, 11 - 11111.
        Если получено одно из четырех 5-битовых кодовых слов, то соответствующие ему два бита являются правильной информацией. Если произошла ошибка, то значит полученное 5-битовое слово, отличается от кодовых слов. В этом случае находят наиболее вероятное переданное слово и берут его в качестве оценки исходных двух битов информации. Например, если мы приняли 01100, то полагаем, что передавалось 01110, и, следовательно, информационное слово равнялось 10.
         В приведенном примере код не является "хорошим", так как он не позволяет исправлять многие конфигурации ошибок. Коды желательно выбирать таким образом, чтобы каждое кодовое слово по возможности больше отличалось от каждого другого и особенно, когда длина блока велика.
        Определить требования к "хорошему коду" и затем предпринять машинный поиск по множеству всех возможных кодов не даст искомого результата, так как каждое кодовое слово представляет собой последовательность из n двоичных символов, и всего имеется 2^k таких слов. Следовательно, код описывается n2^k двоичными символами. Всего существует 2ⁿ способов выбора этих двоичных символов и число различных n,к-кодов равно этому числу. Конечно, многие из этих кодов не соответствуют требованиям (как в случае, когда два кодовых слова равны), поэтому надо либо проверять это по ходу поиска, либо разработать такой алгоритм поиска, который позволит исключать такие коды. Например, выберем (n,k) = (40,20) - код, весьма умеренный по современным стандартам. Тогда число таких кодов превзойдет величину 10^{100 000 00} - невообразимо большое число! Следовательно, без соответствующего алгоритма, поиск проводить бессмысленно.
         В общем случае блоковые коды определяются произвольным конечным алфавитом, скажем алфавитом из q символов {0, 1, 2,..., q - 1}. На первый взгляд введение алфавитов, отличных от двоичного, может показаться излишним. Из соображений эффективности, однако, многие современные каналы являются недвоичными, и коды для этих каналов должны быть также недвоичными. На самом деле коды для недвоичных каналов часто оказываются достаточно хорошими, и сам этот факт может служить причиной для использования недвоичных каналов. Двоичные данные источника тривиальным образом представляются символами q-ичного алфавита, особенно если q равно степени двойки, как это обычно и бывает на практике.
        Блоковый код мощности М с алфавита из q символов определяется как множество из М q-ичных последовательностей длины q, называемых кодовыми словами. Если q = 2, то символы называются битами. Обычно М = q^k для некоторого целого k, и мы будем интересоваться только этим случаем называя код (n,к)-кодом. Каждой последовательности из k q-ичных символов можно сопоставить последовательность из n q-ичных символов, являющуюся кодовым словом.
        Имеются два основных класса кодов, блоковые и древовидные коды, рис 3.25. Блоковый код задает блок из k информационных символов n-символьным кодовым словом. Скорость R блокового кода определяется равенством R = k/n. Скорость в общем случае величина безразмерная, которую можно представить как измеренную в единицах бит/бит или символ/символ. Ее следует отличать от другого, называемого тем же термином скорость, понятия измеряющего канальную скорость в бит/с. Используется и другое определение скорости: R = (k/n)Log_eq, единицей которого является нат/символ, где один нат равен Log₂e битов. Принято также определение R = (k/n)Log2q, в котором скорость измеряется в единицах бит/символ.

Рис. 3.25.Основные классы кодов.

         Древовидный код более сложен. Он отображает бесконечную последовательность информационных символов, поступающих со скоростью k…… символов за один интервал времени, в непрерывную последовательность символов кодового слова со скоростью n….. символов за один интервал времени. Если сообщение состоит из большого числа битов, то в принципе лучше использовать один кодовый блок большой длины, чем последовательность кодовых слов из более короткого кода.
         Природа статистических флуктуации такова, что случайная конфигурация ошибок обычно имеет вид серии ошибок. Некоторые сегменты этой конфигурации содержат больше среднего числа ошибок, а некоторые меньше. Следовательно, при одной и той же скорости более длинные кодовые слова гораздо менее чувствительны к ошибкам, чем более короткие кодовые слова, а соответствующие кодер и декодер будут более сложными. Например, предположим, что 1000 информационных битов передаются с помощью (воображаемого) 2000-битового двоичного кода, способного исправлять 100 ошибок. Сравним такую возможность с передачей одновременно 100 битов с помощью 200-битового кода, исправляющего 10 ошибок на блок. Для передачи 1000 битов необходимо 10 таких блоков. Вторая схема также может исправлять 100 ошибок, но лишь тогда, когда они распределены частным образом - по 10 ошибок в 200-битовых подблоках. Первая схема может исправлять 100 ошибок независимо от того, как они расположены внутри 2000-битового кодового слова, т.е. она существенно эффективнее.
        Таким образом, хорошими являются коды с большой длиной блока и чем они длиннее тем лучше. Такие коды, во-первых, сложно найти, а во вторых они трудно реализуемые. О блоковом коде судят по трем параметрам: длине блока n, информационной длине k и минимальному расстоянию d^*. Минимальное расстояние является мерой различия двух наиболее похожих кодовых слов и задается двумя следующими определениями.
         Расстоянием по Хэммингу между двумя q-ичными последовательностями х и у длины n называется число позиций, в которых они различны. Это расстояние обозначается через d(x, у). Например, возьмем х = 10101 и у =01100; тогда имеем d (10101, 01100) = 3. В качестве другого примера возьмем х = 30102 и у = 21103; тогда d (30102, 21103) = 3. Определение - пусть С = {C… , i = 0,..., М - 1} - код, тогда минимальное расстояние кода С равно наименьшему из всех расстояний по Хэммингу между различными парами кодовых слов, т. e. d^* = min d(Ci,Cj). (n, к)-код с минимальным расстоянием d^* называется также (n, k, d^*)-кодом..
        В коде С, выбранном в примере, d(10101,10010) = 3, d(10010,01110) = 3, d(10101,01110) = 4,
d(10010,11111) = 3, d(10101,11111) = 2, d(01110,11111) = 2; следовательно, для этого кода d^* = 2.
         Предположим, что при передаче кодового слово в канале произошла одиночная ошибка, т.е. принятое слово находится на равном 1 расстоянии по Хэммингу от переданного слова. Если же расстояние до каждого другого кодового слова больше чем 1, декодер исправит ошибку. В более общем случае, если произойдет t ошибок и если расстояние от принятого слова до каждого другого кодового слова больше t, то декодер исправит эти ошибки, приняв ближайшее к принятому кодовому слово в качестве действительно переданного, при условии, если d^*>= 2t + 1.
         Иногда удается исправлять конфигурацию из t ошибок даже тогда, когда это неравенство не удовлетворяется. Однако если d^* < 2t + 1, то достоверное исправление любых t ошибок не может быть гарантировано, так как оно будет зависеть от того, какое слово передавалось и какова была конфигурация из t ошибок внутри блока. Геометрическая иллюстрация данного утверждения приведена на рис.3.26.

Рис. 3.26. Сфера декодирования.

         В пространстве всех q-ичных n-последовательностей выбрано некоторое множество n-последовательностей, объявленных кодовыми словами. Если d^* - минимальное расстояние этого кода, at- наибольшее целое число, удовлетворяющее условию d^*>= 2t + 1, то вокруг каждого кодового слова можно описать непересекающиеся сферы радиуса t. Принятые слова, лежащие внутри сфер, декодируются как кодовое слово, являющееся центром соответствующей сферы. Если произошло не более t ошибок, то принятое слово всегда лежит внутри соответствующей сферы и декодируется правильно.
         Некоторые принятые слова, содержащие более t ошибок, попадут внутрь сферы, описанной вокруг другого кодового слова, и будут декодированы неправильно. Другие принятые слова, содержащие более t ошибок, попадут в промежуточные между сферами декодирования области. В зависимости от применения, данный случай можно интерпретировать следующим образом. Неполный декодер декодирует только те принятые слова, которые лежат внутри сфер декодирования, описанных вокруг кодовых слов. Остальные принятые слова, содержащие более допустимого числа ошибок, декодер объявляет нераспознаваемыми. Такие конфигурации ошибок при неполном декодировании называются неисправляемыми. Большинство используемых декодеров являются неполными декодерами.
        Полный декодер декодирует каждое принятое слово в ближайшее кодовое слово. Геометрически это представляется таким образом, что полный декодер разрезает промежуточные области на куски и присоединяет их к сферам так, что каждая точка попадает в ближайшую сферу. Обычно некоторые точки находятся на равных расстояниях от нескольких сфер, тогда одна из этих сфер произвольно объявляется ближайшей. Если происходит более t ошибок, то полный декодер часто декодирует неправильно, но бывают и случаи попадания в правильное кодовое слово. Полный декодер используется в тех случаях, когда лучше угадывать сообщение, чем вообще не иметь никакой его оценки.
         На практике полагают, что в некоторых каналах кроме ошибочного приема происходит и стирание символов, а в конструкции приемников таких каналов предусматривается объявление символа стертым, если он получен ненадежно или если приемник распознал наличие интерференции или сбой. При входном алфавите мощности q такого канала, выходной алфавит имеет мощность q + 1, здесь дополнительный символ называют стирающим. Например, стирание символа 3 в сообщении 12345 приводит к слову 12-45 (не следует путать с другой операцией, называемой выбрасыванием, которая дает 1245).
         Подобные каналы могут использовать коды, контролирующие ошибки. В случае когда минимальное расстояние кода равно d*, любая конфигурация из р стираний может быть восстановлена, если d^*>= р + 1. Далее, любая конфигурация из v ошибок и р стираний может быть декодирована при условии, что
d^*>= 2v + 1 + р. Для доказательства выбросим из всех кодовых слов те р компонент, в которых приемник произвел стирания. Это даст новый код, минимальное расстояние которого не меньше d^*- p , следовательно, v ошибки могут быть исправлены при условии, что выполняется приведенное выше неравенство. Таким образом, можно восстановить укороченное кодовое слово с р стертыми компонентами. Наконец, так как d^* > р + 1, существует только одно кодовое слово, совпадающее с полученным в нестертых компонентах, то исходное кодовое слово может быть восстановлено.